package classical_problems_150;

public class P_0209 {

    public int minSubArrayLen1(int target, int[] nums){
        // 这是根据前缀和进行全局搜索的方法，耗时O(n^2)
        int[] pre_sum = new int[nums.length];
        pre_sum[0] = nums[0];
        for(int i=1; i<nums.length; i++){
            pre_sum[i] = pre_sum[i-1] + nums[i];
        }
        int res = nums.length+1;
        for(int i=0; i<nums.length; i++){
            for(int j=i; j<nums.length; j++){
                int len = j -i + 1;
                int sum = pre_sum[j] - pre_sum[i] + nums[i];
                if(sum >= target){
                    res = Math.min(res, len);
                }
            }
        }
        if(res > nums.length) res = 0;
        return res;
    }

    private int binarySearch(int[] pre_sum, int left, int right, int target){
        int sum_i = pre_sum[left];
        while(right > left){
            int mid = (left + right) / 2;
            int value = pre_sum[mid] - sum_i;
            if(value < target){
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public int minSubArrayLen(int target, int[] nums){
        // 这是根据前缀和进行全局搜索的方法，耗时O(n^2)
        int[] pre_sum = new int[nums.length];
        pre_sum[0] = nums[0];
        for(int i=1; i<nums.length; i++){
            pre_sum[i] = pre_sum[i-1] + nums[i];
        }
        int res = nums.length + 1;
        for(int i=0; i<nums.length; i++){
            int index = this.binarySearch(pre_sum, i, nums.length, target-nums[i]);
            if(index <= nums.length-1){
                int len = index -i +1;
                res = Math.min(len, res);
            }
        }

        if(res > nums.length) return 0;
        return res;
    }



    public static void main(String[] args){
        P_0209 solution = new P_0209();
        int[] nums = {1, 2, 3, 4, 5};
        solution.minSubArrayLen(11, nums);
    }
}
